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.