В одній із зіркових систем Галактичної Республіки сталося зухвале пограбування банку "13-е Товариство міжгалактичного кредиту", з якого було викрадено кілька мільярдів буказоїдів. Виявилося, що Армія Республіки в даному секторі має обмежені сили і не в змозі блокувати всі можливі шляхи втечі грабіжників, тому постало завдання мінімізувати кількість кордонів.

Зоряні системи з'єднуються за допомогою транспортних коридорів. Один армійський кордон може надійно блокувати лише один транспортний коридор. Відомо, що грабіжники ще не встигли залишити пограбовану зіркову систему. Крім цього відомо безліч систем, в яких грабіжники можуть сховатися. Завдання армії полягає в тому, щоб розмістити мінімальну кількість кордонів таким чином, щоб грабіжники не могли потрапити до жодної з цих систем.

Формат вхідних даних

Першим числом у потоці вхідних даних задається загальна кількість \(N\) всіх зіркових систем у галактиці (\(2 ≤ N ≤ 1000\)). Ми припускатимемо, що всі зіркові системи пронумеровані від 1 до \(N\). Система, в якій сталося пограбування, має номер 1.

Далі вводиться ціле число \(H\), що означає кількість систем, в яких грабіжники можуть сховатися.

Потім перераховуються \(H\) цілих чисел \(s_i\) (\(1 ≤ i ≤ H\)), що задає неповторні номери зіркових систем (\(2 ≤ s_i ≤ N\)) укриття.

Після цього вводиться число транспортних коридорів \(T\) в галактиці. Кожен транспортний коридор \(j\) (\(1 ≤ j ≤ T\)) визначається парою цілих чисел \(f_j, t_j\) (\(f_j ≠ t_j\)) – номерів зоряних систем, які він з'єднує. Транспортний коридор працює лише в одному напрямку від системи \(f_j\) до системи, \(t_j\). Будь-яка пара зоряних систем може бути з'єднана максимум одним транспортним коридором. Транспортна мережа така, що від системи 1 до всіх система \(s_j\) існує шлях, що проходить транспортними коридорами.

Формат вихідних даних

Виведіть спочатку ціле число \(M\) – мінімальна кількість необхідних кордонів. Потім M транспортних коридорів, які мають бути заблоковані. Кожен транспортний коридор має бути виведений як кілька цілих чисел \(f_k, t_k\).

Приклад вхідних даних

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

Приклад вихідних даних

1
4 5