Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Người ta khởi tạo một đồ thị có hướng gồm 109 đỉnh, các đỉnh được đánh số từ 1 đến 109 . 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 st. 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 (m105;st)
  • 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.

Ví dụ Input

Copy
5 1 5
1 2
3 5
3 1
2 3
2 4

Output

Copy
4

Nguồn: NTB Hải Dương


Comments

Please read the guidelines before commenting.


There are no comments at the moment.