#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

const int MAX = 4e5 + 5;

int vis[MAX];
vector<pair<int, int>> adj[MAX];

bool dfs(int u, int p) {
    bool ret = true;
    vis[u] = true;
    for (auto [v, i] : adj[u]) {
        if (!vis[v])
            ret &= dfs(v, i);
        else if (i != p)
            ret = false;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }

    int ret = MAX - 1;
    for (int i=1; i<MAX; i++)
        if (!vis[i] && dfs(i, -1))
            ret--;
    cout << ret << "\n";

    return 0;
}

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0, length = n; i < length; i++)
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ep emplace
#define epb emplace_back
#define scll static_cast<long long> 
#define sz(x) static_cast<int>((x).size())
#define pfll(x) printf("%lld\n", x)
#define ci(x) cin >> x
#define ci2(x, y) cin >> x >> y
#define ci3(x, y, z) cin >> x >> y >> z
#define ci4(w, x, y, z) cin >> w >> x >> y >> z
#define co(x) cout << x << endl
#define co2(x, y) cout << x << " " << y << endl
#define co3(x, y, z) cout << x << " " << y << " " << z << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> PQ;
typedef priority_queue<int, vector<int>, greater<int>> PQG;
typedef priority_queue<P> PQP;
typedef priority_queue<P, vector<P>, greater<P>> PQPG;

const int MAX_N = 1e3, MOD = 1e9 + 7, INF = 1e9;
int n, m;
bool used[MAX_N * MAX_N];
map<char, vector<int>> to[MAX_N];

int main() {
    ci2(n, m);
    rep(i, m) {
        int a, b;
        char c;
        ci3(a, b, c);
        to[a - 1][c].epb(b - 1);
        to[b - 1][c].epb(a - 1);
    }
    
    queue<P> q;
    q.ep(0, n - 1);
    used[n - 1] = true;
    int ans = INF, dist = 0;
    while (!q.empty()) {
        P p = q.front(); q.pop();
        if (p.fi > dist && ans < INF) {
            co(ans);
            return 0;
        }
        dist = p.fi;
        int l = p.se / n, r = p.se % n;
        for (auto &i: to[l]) {
            if (to[r].find(i.fi) == to[r].end()) continue;
            for (auto &j: to[l][i.fi]) {
                for (auto &k: to[r][i.fi]) {
                    if (j == r && k == l) ans = min(ans, 2 * p.fi + 1);
                    if (j == k) ans = min(ans, 2 * p.fi + 2);
                    int tmp = j * n + k;
                    if (!used[tmp]) {
                        q.ep(p.fi + 1, tmp);
                        used[tmp] = true;
                    }
                }
            }
        }
    }
    co(-1);
    return 0;
}
