#1429. PATROL - Tuần tra

Một mạng lưới giao thông gồm địa điểm đánh số từ tới và con đường một chiều đánh số từ tới . Con đường thứ nối từ địa điểm tới địa điểm . Mọi địa điểm đều có thể tới được từ và có thể đi đến được .

Hành trình tuần tra của một cảnh sát giao thông như sau: Xuất phát từ địa điểm , đi theo các con đường đã cho tới địa điểm . Một con đường có thể đi qua nhiều lần nhưng phải đi đúng chiều đã định.

Yêu cầu: Tìm số lượng ít nhất các cảnh sát giao thông thỏa mãn: Có thể vạch hành trình tuần tra cho cảnh sát đó để con đường nào cũng được một cảnh sát giao thông đi qua.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa hai số nguyên .

Dữ liệu ra:

• Ghi ra số 𝑘 tìm được.

Ví dụ:

Dữ liệu vào:

6 8
1 2
1 3
2 4
2 5
3 5
4 6
5 6
6 4

Dữ liệu ra:

3

Giải thích:

• CS đi ;
• CS đi
• CS đi .