E. Databases
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Check attachment.

Example
Input
3 4
1 2 3
1 2 3
1 2 1
2 3 1
3 3 2
Output
1
1
2