该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

Format

Input

Output

Samples

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

8
9

Limitation

1s, 1024KiB for each test case.