Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Edge Pairing
Time Limit: 3000MSMemory Limit: 131072K
Total Submissions: 1157Accepted: 451Special Judge


Given a simple connected undirected graph with n vertices and m edges, where m is even, your task is to find a pairing of the edges such that each pair of edges shares a vertex.


The input contains exactly one test cases. On the first line of the test case there are two integers n and m (3 ≤ n ≤ 20,000, 2 ≤ m ≤ 100,000, m is even) which indicate the size of the graph. Next come m lines each with a pair of integers a and b representing an edge (a, b). The vertices are numbered 1 through n.


If a pairing exists, output it in m2 lines. Each line contains three integers a, b and c in this order, indicating that the edges (a, b) and (b, c) are paired together. If no pairing exists, just output “NO” and nothing else.

Sample Input

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6

Sample Output

1 2 4
1 3 4
4 5 2
4 6 3
5 7 6


Illustration of the sample test case:


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator