| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P179PROF - ROUND 9F - TÌM ĐƯỜNG ĐI |
Tí và đố Tèo một trò chơi trên đồ thị có hướng như sau: Hãy tìm một đường đi trên đồ thị G, xuất phát từ đỉnh 1, đi tới đỉnh N, sau đó trở lại đỉnh 1 và phải đi qua tất cả các cạnh đúng một lần duy nhất. Mỗi lần đi qua một cạnh, cạnh đó sẽ bị xóa đi. Để tăng thêm độ khó cho bài toán, Tí bổ sung thêm điều kiện đồ thị G có thể là đa đồ thị.
Tèo thấy bài toán quá hóc búa. Các bạn hãy giúp Tèo nhé!
Input
Dòng đầu tiên là số lượng bộ test T (T <= 10).
Mỗi bộ test bắt đầu bởi 2 số nguyên N và M (N, M <= 200 000), lần lượt là số đỉnh và số cạnh của đồ thị.
M dòng tiếp theo, mỗi dòng gồm 2 số nguyên u, v cho biết có đường đi 1 chiều từ u tới v.
Output
Với mỗi test, in ra “Yes” nếu tìm được đường đi thỏa mãn, in ra “No” trong trường hợp ngược lại.
Example
Input:
2
4 4
1 2
2 3
3 4
4 1
4 3
1 2
2 3
3 1 Output:
Yes
No
Giải thích test 1: Tồn tại 1 cách đi đó là 1 --> 2 -->3 --> 4 --> 1.
| Được gửi lên bởi: | adm |
| Ngày: | 2017-04-17 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
