#include #define MAXN 100 /* Maximální počet vrcholů a hran */ #define MAXM 100*100 int N, M; /* Počet vrcholů a hran */ int d[MAXN]; /* Stupně vrcholů */ int f[MAXN]; /* První hrana z~každého vrcholu */ struct edge { /* Hrana */ int y; /* Kam vede ($y=-1$ pro použité hrany) */ int n; /* Další z~téhož vrcholu */ } e[2*MAXM+2]; /* $e \mathop{\rm xor} 1$ je opačný směr */ void go(int j) /* Prohledáváni grafu do hloubky */ { int m, y; while (m = f[j]) /* Bermež všechny hrany $m$ vedoucí z~$j$ */ { f[j] = e[m].n; /* Hranu odebereme */ if ((y = e[m].y) >= 0) /* Pokud ještě nebyla použita\dots */ { e[m^1].y = -1; /* \dots\ označíme za použitou `protisměrnou' hranu */ go(y); /* Zavoláme se rekursivě */ M--; /* A snížíme počet zpracovaných hran */ } } printf("%d\n", j); /* Vracíme se zpět $\Rightarrow$ vypisujeme vrcholy */ } int main(void) { int i, j, k, m; scanf("%d", &N); /* Načteme vstup */ for(i=1; i<=N; i++) scanf("%d%d", &j, &k); /* Souřadnice ignorujeme, jsou nanic */ scanf("%d", &M); m = 2; for(i=1; i<=M; i++) { scanf("%d%d", &j, &k); e[m].n = f[j]; /* Zařadíme jeden směr\dots */ f[j] = m; e[m++].y = k; d[j]++; e[m].n = f[k]; /* \dots\ a druhý. */ f[k] = m; e[m++].y = j; d[k]++; } j = 1; /* Hledáme startovní vrchol */ k = 0; for(i=1; i<=N; i++) if (d[i] % 2) j = i, k++; if (k <= 2) go(j); if (M) /* Pokud něco zbylo, řešení neexistuje */ puts("Nemá řešení!"); return 0; }