ADDEDGE

Xem PDF



Tác giả:
Dạng bài
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Người ta khởi tạo một đồ thị có hướng gồm \(10^9\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(10^9\). Ban đầu đồ thị không có cung nào. Người ta lần lượt thêm các cung vào đồ thị bởi \(m\) lệnh dạng \(Add(u,v)\): thêm một cung nối từ đỉnh \(u\) đến đỉnh \(v\) trên đồ thị.

Yêu cầu: Cho trước hai đỉnh \(s\)\(t\). Hãy cho biết số thứ tự của lệnh \(Add\) đầu tiên mà sau thời điểm thực hiện lệnh \(Add\) đó, ta có thể đi từ \(s\) đến \(t\) theo các cung của đồ thị

Input

  • Dòng 1 chứa ba số nguyên dương \(m,s,t \ (m \leq 10^5;s \neq t)\)
  • \(m\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(u,v\) tương ứng là một lệnh \(Add(u,v)\)

Output

  • Một số duy nhất là số thứ tự lệnh \(Add\) tìm được, trong trường hợp không thể đi từ \(s\) đến \(t\) cho dù thực hiện tất cả các lệnh \(Add\) thì ghi số \(0\).

Example

Test 1

Input
5 1 5
1 2
3 5
3 1
2 3
2 4 
Output
4

Bình luận