There is No Alternative

Example

Input

4 4 1 2 3 1 3 3 2 3 3 2 4 3

Output

1 3

inputFormat

Input

4 4 1 2 3 1 3 3 2 3 3 2 4 3

outputFormat

Output

1 3

样例

4 4
1 2 3
1 3 3
2 3 3
2 4 3

1 3