На минатата Македонска Олимпијада по информатика, едно од најголемите изненадувања на настанот беше фактот што најдобриот натпреварувач, Коки, не успеа да освои ниту еден поен на првиот натпревар од Олимпијадата.

Некои суеверни натпреварувачи, следејќи го принципот "ако можеше тоа да му се случи на најдобриот, подобро јас да не ризикувам", го испрашале Коки низ кои градови патувал кога доаѓал на Олимпијадата, и одлучиле дека е најдобро кога ќе патуваат на одреден натпревар, да внимаваат да не посетат одредени три населени места по истиот редослед како што Коки ги посетил при неговото патување.

Бидејќи веќе е доцна да се направи план за патување на МОИ 2013 (кој ги посетил градовите по погрешен редослед ќе видиме на крајот од настанот), направете план за патување на ИОИ 2013, па барем таму да нема "непријатни" изненадувања.

Конкретно, потребно е да напишете програма која, за дадени N населени места (означени со броевите од 0 до N-1), листа на можни патишта кои ги поврзуваат тие населени места и листа на тројки населени места кои не смеат да се посетат по ред, ќе пронајде и отпечати низ колку најмалку патишта треба да се помине, за да се стигне од населеното место означено со 0 до населеното место означено со N-1.

Влез

Во првиот ред се запишани два цели броја N (3 ≤ N ≤ 3000) и R (1 ≤ R ≤ 10000), кои го означуваат бројот на населени места и бројот на патишта, соодветно.

Во секој од следните R редови се запишани по два цели броја Ai и Bi (0 ≤ Ai < Bi < N), кои означуваат дека постои двонасочен пат кој ги поврзува Ai и Bi. Ниту еден пар населени места нема да се појави повеќе од еднаш.

Во следниот ред е запишан еден цел број T (1 ≤ T ≤ 100000), кој го означува бројот на тројки населени места кои не смеат да се посетат еден по друг.

Во секој од следните T редови се запишани по три цели броја Xi, Yi и Zi (0 ≤ Xi, Yi, Zi < N), кои означуваат дека овие градови не смеат да се посетат по непосреден редослед Xi, Yi, Zi (но, можат, на пример, по редослед Yi, Xi, Zi, итн). Xi, Yi и Zi ќе означуваат различни населени места (ќе бидат различни броеви).

Излез

Доколку не постои начин да се стигне од населеното место 0 до населеното место N-1, а притоа да се исполнат сите барања, отпечатете "GRESHKA" (со големи букви, без наводниците). Во спротивно, отпечатете низ колку најмалку патишта треба да се помине, за да се стигне од населеното место означено со 0 до населеното место означено со N-1.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 256 megabytes

Примери

влез
4 5
0 1
2 3
0 2
1 2
1 3
2
0 2 3
0 1 3

излез
3

влез
4 5
0 1
2 3
0 2
1 2
1 3
1
0 1 2

излез
2

влез
3 1
0 1
1
0 1 2

излез
GRESHKA

влез
3 2
0 1
1 2
1
0 1 2

излез
GRESHKA

Објаснување за првиот пример: 0->1->2->3

Објаснување за вториот пример: 0->2->3