მოცემული გაქვთ n m k (n<=2*10^5)

n წვეროების რაოდენობა

m რკალების რაოდენობა

k საწყისი წვერო 

და m ცალი წყვილი

დაწერეთ k დან ყველა წვეროსკენ მინიმალური დაშორება. (პირველ ხაზზე პირველთან დაშორება მეორე ხაზზე მეორესთან და ასე შემდეგ.

Input

3 3 3

1 2

1 3

2 3

Output

1

1

0