| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
SSAM419F - KHÁM PHÁ HÀNH TRÌNH |
Tốt nghiệp đại học, Lina quyết định đi khám phá tất cả các thành phố ở đất nước mình. Có N thành phố và M tuyến đường bộ kết nối chúng với nhau. Lina muốn nghĩ rằng một hành trình thật “đẹp” là hành trình đi qua M-2 tuyến đường đúng hai lần, và đi qua 2 tuyến đường còn lại duy nhất một lần. Lina có thể chọn thành phố xuất phát và kết thúc hành trình là tùy ý. Các bạn hãy tính giúp Lina xem có bao nhiêu cách để lựa chọn một hành trình đẹp? 2 hành trình A và B được coi là khác nhau, nếu như 2 tuyến đường đi qua duy nhất một lần của A và B là khác nhau. Input Dòng đầu tiên là số lượng bộ test T (T ≤ 20). Mỗi test bắt đầu bởi 2 số nguyên N và M (N, M ≤ 100 000). M dòng tiếp theo, mỗi dòng gồm 2 số nguyên u, v cho biết có cạnh nối giữa u và v. Dữ liệu đảm bảo các cạnh không trùng nhau. Có thể có cạnh nối u với chính nó, với mỗi đỉnh u có không quá 1 cạnh như vậy. Output: Với mỗi test, in ra đáp án tìm được trên một dòng. Ví dụ:
|
Input |
Output |
|
3 5 4 1 2 1 3 1 4 1 5 5 3 1 2 2 3 4 5 2 2 1 1 1 2 |
6 0 1 |
Giải thích test 1: Các hành trình thỏa mãn: 2 → 1 → 3 → 1 → 4 → 1 → 5, 2 → 1 → 3 → 1 → 5 → 1 → 4, 2 → 1 → 4 → 1 → 5 → 1 → 3, 3 → 1 → 2 → 1 → 4 → 1 → 5, 3 → 1 → 2 → 1 → 5 → 1 → 4, 4 → 1 → 2 → 1 → 3 → 1 → 5.
| Được gửi lên bởi: | adm |
| Ngày: | 2019-08-09 |
| 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 |
