Description

Format

Input

Output

Samples

2 1
1 2
1 1 2 2

5

Limitation

N<=20000,M<=100000