local mfl, mce = math.floor, math.ceil local mmi, mma = math.min, math.max local bls, brs = bit.lshift, bit.rshift local SegTree = {} SegTree.updateAll = function(self) for i = self.stagenum - 1, 1, -1 do local cnt = bls(1, i - 1) for j = 1, cnt do self.stage[i][j] = self.func(self.stage[i + 1][j * 2 - 1], self.stage[i + 1][j * 2]) end end end SegTree.create = function(self, n, func, emptyvalue) self.func, self.emptyvalue = func, emptyvalue local stagenum, mul = 1, 1 self.stage = {{}} while mul < n do mul, stagenum = mul * 2, stagenum + 1 self.stage[stagenum] = {} end self.stagenum = stagenum for i = 1, n do self.stage[stagenum][i] = i end for i = n + 1, mul do self.stage[stagenum][i] = emptyvalue end self:updateAll() end SegTree.getRange = function(self, left, right) if left == right then return self.stage[self.stagenum][left] end local stagenum = self.stagenum local ret = self.emptyvalue while left <= right do local stage, sz = 1, bls(1, stagenum - 1) local len = right - left + 1 while (left - 1) % sz ~= 0 or len < sz do stage, sz = stage + 1, brs(sz, 1) end ret = self.func(ret, self.stage[stage][1 + brs(left - 1, stagenum - stage)]) left = left + sz end return ret end SegTree.update = function(self, idx, value) for i = self.stagenum - 1, 1, -1 do local dst = brs(idx + 1, 1) local rem = dst * 4 - 1 - idx self.stage[i][dst] = self.func(self.stage[i + 1][idx], self.stage[i + 1][rem]) idx = dst end end SegTree.new = function(n, func, emptyvalue) local obj = {} setmetatable(obj, {__index = SegTree}) obj:create(n, func, emptyvalue) return obj end local n, m = io.read("*n", "*n") local needcnt = {} local edge = {} local used = {} for i = 1, n do needcnt[i] = 0 edge[i] = {} used[i] = false end used[n + 1] = true needcnt[n + 1] = 1000000007 for i = 1, m do local tgt, r = io.read("*n", "*n") needcnt[tgt] = needcnt[tgt] + r for j = 1, r do local a = io.read("*n") edge[a][tgt] = true end end local function merge(x, y) if used[x] then return y end if used[y] then return x end return needcnt[x] < needcnt[y] and x or y end local st = SegTree.new(n + 1, merge, n + 1) local ret = 0 while true do local pos = st.stage[1][1] if n < pos then break end if 0 < needcnt[pos] or used[pos] then break end ret = ret + 1 used[pos] = true st:update(pos) for dst, _u in pairs(edge[pos]) do if not used[dst] then needcnt[dst] = needcnt[dst] - 1 st:update(dst) end end end print(ret)