Ngân khởi tạo một đồ thị có hướng gồm \(10^9\) đỉnh các đỉnh được đánh số từ \(1\) tới \(10^9\), ban đầu đồ thị không có cung nào. Ngân thêm lần lượt các cung vào đồ thị bởi câu lệnh dạng add(u, v), nghĩa là thêm một cung nối từ đỉnh \(u\) tới đỉnh \(v\) trên đồ thị. Cho trước \(2\) đỉnh \(s\) và \(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 đó đỉnh \(s\) có thể đi tới được đỉnh \(t\) theo một số cung của đồ thị.

Dữ liệu vào

• Dòng đầu chứa \(3\) số nguyên \(m \le 10^5, s, t\)
• \(M\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên \(u, v\) thế hiện lệnh add(u, v)

Dữ liệu ra

• Ghi trên \(1\) dòng là kết quả của bài toán. Nếu không tồn tại kết quả thỏa mãn, in ra một số \(0\).

Input 1

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

Output 1

4