/* -*- coding: utf-8 -*- * * 1612.cc: No.1612 I hate Construct a Palindrome - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 10000; const int MAX_M = 20000; /* typedef */ typedef queue qi; typedef pair pii; typedef vector vpii; /* global variables */ vpii nbrs[MAX_N]; char cs[MAX_M]; pii es[MAX_M], ps0[MAX_N], ps1[MAX_N]; int ds0[MAX_N], ds1[MAX_N]; int ts[MAX_N * 2], ts0[MAX_N], ts1[MAX_N]; /* subroutines */ void bfs(int n, int st, int ds[], pii ps[]) { fill(ds, ds + n, -1); ds[st] = 0; ps[st] = pii(-1, -1); qi q; q.push(st); while (! q.empty()) { int u = q.front(); q.pop(); for (auto ve: nbrs[u]) { int v = ve.first; if (ds[v] < 0) { ds[v] = ds[u] + 1; ps[v] = pii(u, ve.second); q.push(v); } } } } int revpath(pii ps[], int gl, int ts[]) { int l = 0; for (int u = gl; ps[u].second >= 0; u = ps[u].first) ts[l++] = ps[u].second; return l; } bool palindrome(int l, int ts[]) { for (int i = 0, j = l - 1; i < j; i++, j--) if (cs[ts[i]] != cs[ts[j]]) return false; return true; } /* main */ int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int u, v; char w[4]; scanf("%d%d%s", &u, &v, w); u--, v--; cs[i] = w[0]; nbrs[u].push_back(pii(v, i)); nbrs[v].push_back(pii(u, i)); es[i] = pii(u, v); } int e0 = nbrs[0][0].second, e1 = -1; for (int i = 0; i < m; i++) if (i != e0 && cs[e0] != cs[i]) { e1 = i; break; } if (e1 < 0) { puts("-1"); return 0; } //printf("e0=%d, e1=%d\n", e0, e1); bfs(n, nbrs[0][0].first, ds0, ps0); bfs(n, n - 1, ds1, ps1); int e1u = es[e1].first, e1v = es[e1].second; if (ds0[e1u] > ds0[e1v]) swap(e1u, e1v); int l0 = revpath(ps0, e1u, ts0); int k = 0; ts[k++] = e0; for (int i = l0 - 1; i >= 0; i--) ts[k++] = ts0[i]; ts[k++] = e1; if (ds1[e1v] > ds1[e1u]) swap(e1v, e1u), ts[k++] = e1; int l1 = revpath(ps1, e1v, ts1); for (int i = 0; i < l1; i++) ts[k++] = ts1[i]; if (palindrome(k, ts)) ts[k + 2] = ts[k + 1] = ts[k], k += 2; printf("%d\n", k); for (int i = 0; i < k; i++) printf("%d\n", ts[i] + 1); return 0; }