G. Graph Coloring Problem
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
5 6 6
1 5 3
2 5 14
1 2 12
2 4 7
4 3 10
2 3 9
3
9
12
15
1
8
Output
2
3
5
5
1
2
Input
2 1 5
1 2 100
98
99
100
101
102
Output
1
1
2
2
2