F3. Tree of Life (hard)

хугацааны хязгаарлалт 8 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

To add insult to injury, the zombies have taken all but two drawings from Heidi! Please help her recover the Tree of Life from only these two drawings.

Оролт

The input format is the same as in the medium version, except that now the bound on n is 2 ≤ n ≤ 1000 and that k = 2.

Гаралт

The same as in the medium version.

Орчуулсан: [орчуулагдаж байгаа]

Жишээ тэстүүд

Оролт
1
9 2
6
4 3
5 4
6 1
8 6
8 2
7 1
5
8 6
8 7
8 1
7 3
5 1
Гаралт
YES
2 1
3 1
5 4
6 5
7 6
8 5
9 8
1 4
Сэтгэгдлүүдийг ачааллаж байна...