Cho đồ thị có hướng gồm ~ n ~ đỉnh và ~ m ~ cung (có hướng). Hãy cho biết trong đồ thị có chu trình hay không?

Dữ liệu vào

+Dòng đầu ghi số nguyên ~ t ~ ~ ( 1 ≤ t ≤ 5 ) ~ là số bộ dữ liệu, tiếp theo là thông tin về ~ t ~ bộ dữ liệu, mỗi bộ bao gồm:

• Dòng đầu ghi 2 số nguyên dương ~ n ~ và ~ m ~ cho biết số đỉnh và số cung của đồ thị.
• ~ m ~ dòng tiếp theo mỗi dòng ghi 2 số ~ u, v ~ cho biết một cung của đồ thị ~ (1≤n, m ≤ 10^5 ) ~

Kết quả

• Với mỗi bộ dữ liệu tương ứng trong input ghi số 0 nếu đồ thị không có chu trình, ngược lại ghi 1. Mỗi số được ghi trên một dòng

Ví dụ:

Input 1

2
3 2
1 2
2 3
2 2
1 2
2 1 

Output 1

0
1