해결한 사람
0
명
정답률
0.00
%
시간 제한
2000
ms
메모리 제한
245
MB
All Berland 주민들은 Berland의 도시 상공에서 Blue Helicopter에 탄 마법사가 펼칠 전례 없는 순회 공연을 기다리고 있다!
Berland에는 n개의 도시가 있고, 그중 일부 도시 쌍은 양방향 도로로 연결되어 있다는 사실이 잘 알려져 있다. 각 도시 쌍은 최대 하나의 도로로 연결된다. 도로망이 연결되어 있다고 보장되지는 않는다. 즉, 어떤 도시에서는 다른 어떤 도시에 도달할 수 없을 수도 있다.
순회 공연은 여러 에피소드로 구성된다. 각 에피소드에서 다음과 같은 일이 일어난다.
마법사는 도로를 이용하는 것을 좋아하지 않는 것으로 알려져 있으므로, 각 도로를 방향과 관계없이 최대 한 번만 이용하는 데 동의한다. 다시 말해, a와 b 사이의 도로에서는 a에서 b로 한 번만 이동하거나, b에서 a로 한 번만 이동하거나, 이 도로를 전혀 이용하지 않을 수 있다.
마법사는 위의 규칙을 위반하지 않으면서 가능한 한 많은 에피소드를 계획하려 한다. 마법사를 도와주자!
마법사는 같은 도시를 여러 번 방문할 수 있으며, 제한은 도로에만 적용된다는 점에 유의하라.
첫 번째 줄에는 Berland의 도시 수와 도로 수를 각각 나타내는 두 정수 n, m (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105)가 주어진다.
이어서 각 줄에 하나씩 도로에 대한 설명이 주어진다. 각 설명은 두 정수의 쌍 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)이며, 여기서 ai와 bi는 i-th 도로로 연결된 도시들의 번호이다. 같은 도시 쌍을 연결하는 두 도로는 존재하지 않음이 보장된다. 모든 도로는 양방향이다. 도시에는 1부터 n까지 번호가 매겨져 있다.
Berland의 도로망은 연결되어 있지 않을 수도 있다.
첫 번째 줄에 가능한 에피소드 수의 최댓값 w를 출력한다. 이어지는 w개의 줄에는 마법사가 방문하는 순서대로 도시의 번호를 나타내는 세 정수 x, y, z 형식으로 에피소드를 출력해야 한다.
4 5
1 2
3 2
2 4
3 4
4 1
2
4 3 2
4 2 1
5 8
5 3
1 2
4 5
5 1
2 5
4 3
1 4
3 2
4
1 5 4
3 5 2
1 2 3
3 4 1