Input

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

Output

4
1

Giới hạn:

Subtask1: n<=30
Subtask2: n<=300
Subtask3: n<=3000

Nguồn: 3D '1819