#include #include #include #include #include #include using namespace std; const int MAX_STATION = 1024; int n, m; int arrive[MAX_STATION]; int leave[MAX_STATION]; typedef vector > Train; vector train; struct ArriveTraits { int impossible() const { return 1<<29; } bool cmp(int a, int b) const { return a < b; } Train::const_iterator begin(const Train& s) const { return s.begin(); } Train::const_iterator end(const Train& s) const { return s.end(); } }; struct LeaveTraits { int impossible() const { return -1; } bool cmp(int a, int b) const { return a > b; } Train::const_reverse_iterator begin(const Train& s) const { return s.rbegin(); } Train::const_reverse_iterator end(const Train& s) const { return s.rend(); } }; template struct State { const Train& t; int i; bool exist; Traits tr; State(const Train& tt, int ii, bool e) : t(tt), i(ii), exist(e) {} pair current() const { return tr.begin(t)[i]; } bool nextState() { return ++i < (int)t.size(); } bool operator <(const State& b) const { return tr.cmp(current().second, b.current().second); } }; template void CalcTime(int* output, int src_p, int src_t, Traits tr) { fill_n(output, n, tr.impossible()); multiset > up; output[src_p] = src_t; for(int i = 0; i < m; ++i) up.insert(State(train[i], 0, false)); while(!up.empty()) { State s = *up.begin(); up.erase(up.begin()); pair cur = s.current(); if(!tr.cmp(cur.second, output[cur.first])) s.exist = true; if(s.nextState()) { pair next = s.current(); if(s.exist && tr.cmp(next.second, output[next.first])) output[next.first] = next.second; up.insert(s); } } } int Solve(int src_p, int src_t, int dst_p, int dst_t) { CalcTime(arrive, src_p, src_t, ArriveTraits()); if(arrive[dst_p] > dst_t) return -1; CalcTime(leave, dst_p, dst_t, LeaveTraits()); int ans = 0; for(int i = 0; i < m; ++i) { const Train& st = train[i]; int s = -1, t = -1; for(int j = 0; j < (int)st.size(); ++j) { if(s < 0 && arrive[st[j].first] <= st[j].second) s = j; if(leave[st[j].first] >= st[j].second) t = j; } if(s >= 0 && t >= 0) ans = max(ans, st[t].second - st[s].second); } return ans; } int ReadTime(istream& s) { int h, m; char c; s >> h >> c >> m; return h*60 + m; } int ReadPos(istream& s) { int p; s >> p; --p; return p; } int main() { ifstream cin("D.txt"); while(cin >> n >> m && n) { int sp = ReadPos(cin); int st = ReadTime(cin); int dp = ReadPos(cin); int dt = ReadTime(cin); train.resize(m); for(int i = 0; i < m; ++i) { int k; cin >> k; train[i].resize(k); for(int j = 0; j < k; ++j) { train[i][j].first = ReadPos(cin); train[i][j].second = ReadTime(cin); } } int ans = Solve(sp, st, dp, dt); if(ans >= 0) cout << ans << endl; else cout << "impossible" << endl; } }