DLX

Dancing Link X 求精确覆盖与重复覆盖入门

Posted on

DLX算法入门文……主要说一下我对这个算法的理解。

问题描述

精确覆盖问题:

以矩阵模型介绍,给你一个矩阵,其每个格子的权值范围是 [0,1] ,让你选出若干行,使得选出的行的 1 覆盖了一行的所有格子,且不能有重叠。

重复覆盖问题:

与精确覆盖问题基本相同,但是所选的行集合中,同一列的 1 允许重叠。
这个问题当然不可能让你输出可行方案,输出的应该是行数最小的方案。

算法理解

精确覆盖和重复覆盖都是NP问题,通常的,我们只能通过搜索去解决它。事实上DLX算法也是基于搜索算法。这里放上我的学习博客,里面讲的非常详细,一般人写的博客已然不会超过他。
所以我写这个个人理解其实主要是给自己看的。

首先最容易的当然是 \( 2^{row} \) 的最简单的裸搜,这谁都想得到……而且复杂度很高……

其实当我们选中一行时,对于这一行的每一个 1 元素,含有与选中行同一列的 1 元素的行自然是不能选的,与此同时对于选中行每一个 1 元素,它所在的列其实我们也已经不再需要去考虑它们,因此,我们可以把这些元素删除,得到一个新的矩阵,如此重复操作,直到能覆盖一行的所有格子。

基本的原理就是这些,因为涉及到非常多的增删数据,使用链表是非常非常高效且合理的!!
因为给定的图一般是稀疏图,所以如果只记录 1 的位置将会非常省内存。

而对于重复覆盖,与精确覆盖基本一致,因为找最小的原因,还可以加一个 A * 优化。

入门实践与模板

HihoCoder 1317 搜索四·跳舞链

题意:
最基本的精确覆盖入门题

思路:
模板题……

而且非常意外的发现网上的模板相似度非常高!!
所以我这里也就改了一蛤变量名就没了。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string.h>
#include <string>
#include <utility>
#include <vector>

#define ll long long

using namespace std;

const int maxnode = 1e5 + 10;
const int maxm = 1e3 + 5;
const int maxn = 1e3 + 5;

struct DLX {
    int n, m, size;
    int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; //L,R,D,U四个数组记录某节点上下左右邻居
    int head[maxn], ccnt[maxm];                                                     //head记录排头,ccnt记录某列有多少个节点
    int ansd, ans[maxn];
    void init(int _n, int _m)
    {
        n = _n;
        m = _m;
        for (int i = 0; i <= m; i++) {
            ccnt[i] = 0;
            U[i] = D[i] = i;
            L[i] = i - 1;
            R[i] = i + 1;
        }
        R[m] = 0;
        L[0] = m;
        size = m;
        for (int i = 1; i <= n; i++)
            head[i] = -1;
    }

    void link(int r, int c)
    {
        ++ccnt[Col[++size] = c];
        Row[size] = r;
        D[size] = D[c];
        U[D[c]] = size;
        U[size] = c;
        D[c] = size;
        if (head[r] < 0)
            head[r] = L[size] = R[size] = size;
        else {
            R[size] = R[head[r]];
            L[R[head[r]]] = size;
            L[size] = head[r];
            R[head[r]] = size;
        }
    }

    void exactRemove(int c)
    {
        L[R[c]] = L[c];
        R[L[c]] = R[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                --ccnt[Col[j]];
            }
    }

    void repeatRemove(int c)
    {
        for (int i = D[c]; i != c; i = D[i])
            L[R[i]] = L[i], R[L[i]] = R[i];
    }

    void repeatResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            L[R[i]] = R[L[i]] = i;
    }

    int f()
    {
        bool vv[maxm];
        int ret = 0, c, i, j;
        for (c = R[0]; c != 0; c = R[c])
            vv[c] = 1;
        for (c = R[0]; c != 0; c = R[c])
            if (vv[c]) {
                ++ret, vv[c] = 0;
                for (i = D[c]; i != c; i = D[i])
                    for (j = R[i]; j != i; j = R[j])
                        vv[Col[j]] = 0;
            }
        return ret;
    }

    void repeatDance(int d)
    {
        if (d + f() >= ansd)
            return; //估价函数剪枝,A*搜索
        if (R[0] == 0) {
            if (d < ansd)
                ansd = d;
            return;
        }
        int c = R[0], i, j;
        for (i = R[0]; i; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        for (i = D[c]; i != c; i = D[i]) {
            repeatRemove(i);
            for (j = R[i]; j != i; j = R[j])
                repeatRemove(j);
            repeatDance(d + 1);
            for (j = L[i]; j != i; j = L[j])
                repeatResume(j);
            repeatResume(i);
        }
    }

    void exactResume(int c)
    {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j])
                ++ccnt[Col[U[D[j]] = D[U[j]] = j]];
        L[R[c]] = R[L[c]] = c;
    }

    //d为递归深度
    bool exactDance(int d)
    {
        if (R[0] == 0) {
            ansd = d;
            return true;
        }
        int c = R[0];
        for (int i = R[0]; i != 0; i = R[i])
            if (ccnt[i] < ccnt[c])
                c = i;
        exactRemove(c);
        for (int i = D[c]; i != c; i = D[i]) {
            ans[d] = Row[i];
            for (int j = R[i]; j != i; j = R[j])
                exactRemove(Col[j]);
            if (exactDance(d + 1))
                return true;
            for (int j = L[i]; j != i; j = L[j])
                exactResume(Col[j]);
        }
        exactResume(c);
        return false;
    }

    void output()
    {
        printf("%d", ansd);
        for (int i = 0; i < ansd; i++)
            printf(" %d", ans[i]);
        puts("");
    }
};

DLX dlx;
int main()
{
    int n, m, T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        dlx.init(n, m);
        for (int i = 1, num; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%d", &num);
                if (num == 1)
                    dlx.link(i, j);
            }
        if (!dlx.exactDance(0))
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}
Rails

第一个Rails半成品的一些经验

Posted on

简单说就是数据库课设,趁我现在保留着对整个程序的开发过程,这里简单阐述一些过程。
因为以前忘的多了,加上比赛啊,什么的,有点赶,还有两个功能没能实现,不过勉强还是能拿出手

主要学习来源
向作者ihower致敬

顺便在最前面展示一下成果主页
主页

Rails 核心思想

众所周知,Rails 以开发速度闻名,我写完统计了一下代码量,所有代码应该不包含注释也不过 400 行多一点。
代码统计
而其核心思想在于规定化,也可说是标准化。用一些内置函数去生成代码。
举个例子,在路由(Route)上,根据MVC规则,每一个网址都应该有一条路由与之相对应。rails则使用标准化的RESTful
而因为是函数,所以它的参数都必须与其相对应,所照成的缺陷也很显然,内置函数使用上限不足,完美自定义的网站仍需要自己去架构。为此Rails 也构造了更多的内置函数,为的是提高总体使用上限。当然所造成的结果会是有一些函数的作用重叠。但这并不影响,反而完全符合Ruby的哲学。

Rails 各目录简介

  • app/assets 保存着各种样式文件 包括css,js,和一些图片
  • app/controller 保存着控制器文件
  • app/helper 保存着各个控制其对应的自定义helper文件,关于helper,请移步 传送门
  • app/models 保存着各个模型文件
  • app/views 保存着各个视图文件
  • bin 一些二进制文件,不同管它
  • cofig 配置文件目录,包含了开发环境(environments),初始化配置(initializers),数据库配置(database.yml),路由配置(routes.rb) 等
  • db 数据库相关,其中的子目录 migrate 是数据库迁移文件目录
  • lib 不知道干嘛用,也没用过
  • log 日志文件目录,包含三个环境运行Rails的日志及其他日志
  • public 公共目录,一些共有的文件(比如一些上传文件)都会默认保存在这个目录
  • vendor 没用过…………
  • 其他在根目录但不在任何目录的重要一点的文件也就 Gemfile 和 README.md 了,README都知道的,gemfile 保存着在项目中需要的一些 gem

几个常用helper

form_for

一个最常用也是最需要掌握的是 form_for 表格生成 helper
form_for有些复杂,最好还是移步 RailsAPI
一般是 form_for 对象, 路径, 选项, 块
其中对象必不可缺,其他都是可以缺省的

image_tag与 image_path

image_tag(路径,选项) 用于显示图片
image_path(不带后缀的图片名) 用于寻找图片并生成图片路径,一般优先在 app/assets 中查找

link_to

字面意思,就是链接,一般用法为
link_to 链接名, 链接路径, 选项, 块

button_to 与 button_tag

button_tolink_to极为相似,但毕竟是 button,button_to的type内置为 submit 无法修改,若要更高的自由度,就得使用 button_tag
用法基本一致

link_to 链接名, 链接路径, 选项, 块
link_tag 链接名, 链接路径, 选项, 块

为只为样式使用按钮而不用链接,可以在button_tag的基础上加个onclick属性即可

几个相关gem

这里不发链接了,在github输一下就找到了

  • bootstrap-sass 使用bootstrap的基础
  • bootstrap-datepicker-rails 优秀的日期选择
  • ransack 自定义筛选
  • devise 用户注册管理
  • rolify 用户角色管理
  • cancancan 用于权限管理
  • carrierwave 文件上传

几个新人容易出错的地方

  • rails 的 css 在开发过程中是默认锁定的,所以你在 css 中增加样式默认没有任何变化
  • 关于资料验证和必填属性,资料验证(params)一般来说没有选择性,你必须吧所有元素都填上,而必填属性(validates_presence_of) 则可以自由选择
  • 在建立项目之前务必理清楚数据对象之间的关系,当然如果搞错了也可以新建迁移(migrate),若要重建model,必须删除同名表,操作为 进入rails控制台 rails c,输入 ActiveRecord::Migration.drop_table(:users) # users is table name
  • flash 是一种“闪存”变量,这种变量你一刷新,它所保存的东西就没了,其值为 nil
  • 设置路由的时候难免会有冲突,优先级从上往下

暂时只想到这么多,其他的东西都能在最上面的学习资料中找到,我这里只讲了一些个人经验。

树形DP

CodeForces 855 C Helga Hufflepuff’s Cup

Posted on

前几天的上分场的树形DP

我敢说思路和我当时想得已经一模一样了,还有半个多小时的时候,gou bi 带鱼说把题目给他看一下,然后立马得出,树形DP解不了,肯定是树分治!
当时我在一个子问题上走不出来,于是就信了,然后开始划水……

md

题意:
给你一棵树,要你给树上的每一个节点赋值,赋值存在范围,再给你一个特殊值,除开特殊值意外的数值赋值次数不限,但是特殊值的相邻节点的值不能是特殊值,也不能是比特殊值大的值。
问方案数。

思路:
首先值得注意的是,特殊值赋值次数不超过10,这是一个重要突破口,这使得树形DP的解法存在可能性。
简单说就是在每个节点都保存当前节点为根节点的子树分别含有 [ 0, 10 ] 个特殊值的方案数。
但这还不好决策转移,我们还需要对当前值的范围作为状态进行判断。
我在比赛中只用了,当前值为特殊值,和不是特殊值两个状态,但是现在看了其他人的代码,发现三个状态更容易。
当前节点赋值小于特殊值,大于特殊值,等于特殊值。这样就很好转移,不细说,看代码都能秒懂。

我在比赛时候被卡的子问题是这样的,对于计算当前子树的特殊值数量为 n 的时候,我必须将当前根节点的每一个孩子的状态都理清楚。
比如说数量为 3 ,有三个孩子A,B,C
那么其方案数就是以下情况累加

  • \( A_0+B_0+C_3 \)
  • \( A_0+B_3+C_0 \)
  • \( A_3+B_0+C_0 \)
  • \( A_1+B_0+C_2 \)
  • \( A_0+B_1+C_2 \)
    ……
    ……

:wc 好多,复杂度好高,这不是组合问题么???
现在看来真是煞笔……

AC Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

int n, m, k, x;
vector<int> tree[maxn];

ll dp[maxn][3][11];
ll tmp[3][11];

void dfs(int u, int par)
{
    dp[u][0][0] = k - 1;
    dp[u][1][0] = m - k;
    dp[u][2][1] = 1;
    for (auto v : tree[u]) {
        if (v != par) {
            dfs(v, u);
            memset(tmp, 0, sizeof tmp);
            for (int i = 0; i <= x; i++)
                for (int j = 0; i + j <= x; j++) {
                    tmp[0][i + j] = (tmp[0][i + j] + dp[u][0][i] * (dp[v][0][j] + dp[v][1][j] + dp[v][2][j])) % mod;
                    tmp[1][i + j] = (tmp[1][i + j] + dp[u][1][i] * (dp[v][0][j] + dp[v][1][j])) % mod;
                    tmp[2][i + j] = (tmp[2][i + j] + dp[u][2][i] * dp[v][0][j]) % mod;
                }
            for (int i = 0; i <= x; i++)
                for (int j = 0; j < 3; j++)
                    dp[u][j][i] = tmp[j][i];
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    scanf("%d%d", &k, &x);
    dfs(1, 0);
    int ans = 0;
    for (int i = 0; i <= x; i++)
        for (int j = 0; j < 3; j++)
            ans = (ans + dp[1][j][i]) % mod;
    printf("%d\n", ans);
    return 0;
}
Rails

Rails 使用 carrierwave 上传文件

Posted on

……崩溃,找了很久的资料,最后找到一份template才解决问题。

carrierwave是一个rails 上传文件的 gem,然而用不来……
作者在 github 上的文档真的很没有条理性

前言

偶然间看到这篇文章,希望读者也可以多思考一下。
现在框架发展这么迅速,各种api泛滥,我们在寻求解决一个问题的时候,往往会有点急功近利。如果你考虑了底层实现,那你才是真正学到了东西,并能广泛运用它。否则,你顶多只是积累了当前框架或者api的使用经验。换了一个框架你就完全不会了。

但我的确是看完了这篇文章,我也的确去思考了,但是还是不会用!!!
因为网上很多文章和博客都忽略了一个非常重要的地方,下面我会说明。

这里详细介绍一下 carrierwave 的用法,并假设你已经开了上面那篇文章并思考过了。

安装

首先是安装,在gemfile中输入 gem 'carrierwave', '~> 1.0' 并执行 bundle install

carrierwave 实际建立的是 model ,但这里便于区分并且生成的类同时也是 uploader ,输入命令

rails generate uploader Image

这里的 Image 是由你自己取名的 uploader ,输完后就会生成一个 ruby文件,关于文件上传的一些设置一般都是在这个文件中。

app/uploaders/image_uploader.rb

View

根据MVC,我们先写 views ,一般是在某个目录下的 new.html.erb

<%= form_for @comic, :url => comics_path,:html => {:multipart => true} do |t|%>
# 其他代码

    <br><%= t.label :image, '漫画封面' %></br>
    <%= t.file_field :image %>
    <%= t.hidden_field :image_cache %>

# 其他代码
<% end %>

这里一定一定一定要注意, :html => { :multipart => true } 这个hash一定要加!!!只有加了这个才能上传文件,别问我什么意思,什么道理,我不知道……

Controller

然后是controller,一般为 某个目录下的 create 函数
其实在controller只要和平常一样操作即可,这里还是放上我写的吧

  def create
    @comic = Comic.new(comic_params)

    if @comic.save
        # 其他代码
    else
        # 其他代码
    end
  end

Uploader 的 其他配置

太复杂的高级用法我就不说了,更何况我自己也不会

在预生成的 *_uploader.rb 文件中, 你可以通过重载若干函数来实现你的自定义

store_dir

非重载函数,意思为上传目录,上传目录的相对路径根目录在 public,路径问题上你可以自己设置

extension_whitelist

重载函数,意思为上传文件白名单,默认为所有文件

filename

重载函数,用途为更改文件名,默认和 变量 original_name 相同

default_url

重载函数,虽然没用过,但是看文档还是看懂了,意为默认文件,如果你没有上传任意文件,就将你设置的 default_url 传给你 new 的对象

其他就不是很清楚了。

图片的使用

因为在我的课设中只会上传图片,这里说一下上传图片的使用

因为新增加的类是 uploader ,它实质上有很多属性,比如,filename, original_name, store_dir, url 等等
,而我们显示图片其实只需要一个 url 即可。

在 View 中输入

<%= image_tag comic.image_url %>

就可以显示当前 comic 的 image

矩阵快速幂

计蒜客 Coin 附带矩阵加速模板

Posted on

大概是第5次写矩阵快速幂……
这道题在DP还是矩阵上都是属于简单范畴……,但没想到用DP就很烦……

感觉矩阵加速还是挺有必要学一下的……

顺带学了一下什么叫分数取模用逆元

题意:
让你抛 k 次 硬币,求上面朝上的次数为偶数的概率。
单次正面朝上的概率为 \( \dfrac {q} {p} \)

思路:
令 dp [ n ] [ 0 ] 表示抛了 n 次后,朝上次数为偶数的概率,dp[ n ] [ 1 ] 则表示奇数的概率。
得转移方程
$ dp[n][0] = \dfrac {p-q} {p} \times dp[n-1][0] + \dfrac {q} {p} \times dp[n-1][1] $
$ dp[n][1] = \dfrac {q} {p} \times dp[n-1][0] + \dfrac {p-q} {p} \times dp[n-1][1] $

然后矩阵加速一下就解决了……

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int max_n = 5;
const int mod = 1e9 + 7;

struct Matrix {
    int mat[max_n][max_n], n;
    Matrix(int _n = 1)
    {
        n = _n;
        memset(mat, 0, sizeof mat);
    }
    Matrix operator*(const Matrix& a) const
    {
        Matrix tmp(n);
        for (int i = 1; i < n; ++i)
            for (int j = 1; j < n; ++j)
                if (mat[i][j])
                    for (int k = 1; k < n; ++k)
                        tmp.mat[i][k] = (tmp.mat[i][k] + 1LL * mat[i][j] * a.mat[j][k] % mod) % mod;
        return tmp;
    }
    Matrix Pow(ll m)
    {
        Matrix ret(n), a(*this);
        for (int i = 1; i < n; i++)
            ret.mat[i][i] = 1;
        while (m) {
            if (m & 1)
                ret = ret * a;
            a = a * a;
            m >>= 1;
        }
        return ret;
    }
};

ll fastPow(ll n, ll m)
{
    ll ret = 1;
    while (m) {
        if (m & 1)
            ret = ret * n % mod;
        m >>= 1;
        n = n * n % mod;
    }
    return ret;
}

int main()
{
    int T;
    ll p, q, k;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld %lld", &p, &q, &k);
        ll up = q * fastPow(p, mod - 2) % mod;
        ll down = (p - q) * fastPow(p, mod - 2) % mod;
        if (k == 1) {
            printf("%lld\n", up);
            continue;
        }
        Matrix base(3), res(3);
        base.mat[1][1] = down, base.mat[1][2] = up;
        base.mat[2][1] = up, base.mat[2][2] = down;
        res = base.Pow(k);
        printf("%d\n", res.mat[1][1]);
    }
    return 0;
}
暴力

hihocoder 1513 小Hi的烦恼

Posted on

别看了……bitset入门题……

bitset就是将32个01位操作整合成一个32位整数,一次位操作。
作为一个位运算的优化方法,可以省去 \( 2^5 \)的时间复杂度。
有些大佬 sb 就故意让你 \( O ( n^2 ) \)过不了,加个 bitset 优化就可以卡过去了。
不过也可以说是一个很巧妙的操作。

这题是今晚出去撸串的时候听其他三个沙雕吹的一道题,今晚补上。

题意:
给你一群学生每门功课的排名,总共 5 门学科,问你对于每个学生,所有成绩排名都比他高的学生数有多少。

不存在共列一个名次的数据。

思路:
很暴力……
直接\( n^2 \) + bitset 优化就可以卡过

但是不知道为什么,我的循环在 [ 1, n ] 就 T 了,[0, n ) 就 A 了……

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3e4 + 5;

bitset<maxn> up[5][maxn], res;
int rnk[maxn], rrnk[5][maxn];

int main()
{
    int n;
    scanf("%d", &n);
    each(i, n) each(j, 5) scanf("%d", &rrnk[j][i]);
    each(c, 5)
    {
        each(i, n) rnk[rrnk[c][i]] = i + 1;
        range(i, 2, n)
        {
            up[c][rnk[i]] = up[c][rnk[i - 1]];
            up[c][rnk[i]][rnk[i - 1]] = 1;
        }
    }
    range(i, 1, n)
    {
        res = up[0][i] & up[1][i] & up[2][i] & up[3][i] & up[4][i];
        printf("%ld\n", res.count());
    }
    return 0;
}
树形DP

CodeForces 19E Fairy

Posted on

一道二分图性质的应用 + 树形DP ?

看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些

题意:
给你一个图,让你删除一条边,使得剩下的图是二分图。
输出可删边数并顺序输出边的序号。

思路:
首先你必须知道判定二分图的充要条件 —— 不存在奇环。
如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。
但是这里必须让你删掉一条边……

写不来……感觉不好写,最后无奈去看题解了……

先整理一下判断思路:

  1. 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件
  2. 覆盖了所有的奇环,并且不能覆盖偶环的所有边

为什么同时不能覆盖偶环,这个我还真没想到,但是在纸上画一画就是很显然的了,同时覆盖奇环和偶环的边删去后,两个环会变成一个新的环,偶数+奇数 还是奇数。所以不能覆盖偶环。

因此得出如下具体实现,随便生成一棵生成树,用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。
如果奇环数量大于 1 ,那么非树边必定不可能是满足条件的,因为非树边最多只能覆盖一个环,两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的时候才需要我们去考虑,如果该非树边覆盖了奇环,则删之。
而对于树边,判断其覆盖奇环数和偶环树是否满足条件即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;
int n, m, top, cnt;

pii edges[maxm];
int head[maxn];
int idx;

int odd[maxn], even[maxn];
int dep[maxn], edge_type[maxm];
bool vis[maxn];

void addEdge(int u, int v)
{
    edges[idx] = make_pair(v, head[u]);
    head[u] = idx++;
    edges[idx] = make_pair(u, head[v]);
    head[v] = idx++;
}

void dfs(int u, int e)
{
    vis[u] = true;
    dep[u] = ++top;
    int v;
    for (int id = head[u]; ~id; id = edges[id].second) {
        if (edge_type[id] == -1)
            continue;
        v = edges[id].first;
        if (!vis[v]) {
            edge_type[id] = edge_type[id ^ 1] = -1;
            dfs(v, id >> 1);
            odd[e] += odd[id >> 1];
            even[e] += even[id >> 1];
        } else {
            if (edge_type[id] == 1)
                odd[e]--;
            else if (edge_type[id] == 2)
                even[e]--;
            else {
                if ((dep[u] - dep[v]) & 1)
                    even[e]++, edge_type[id] = edge_type[id ^ 1] = 2;
                else
                    odd[e]++, edge_type[id] = edge_type[id ^ 1] = 1, cnt++;
            }
        }
    }
    top--;
}

int ans[maxn], anum;

int main()
{
    int u, v;
    scanf("%d %d", &n, &m);
    fill(head, head + n + 1, -1);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; i++)
            printf("%d ", i);
    } else {
        for (int i = 0; i < m; i++)
            if (odd[i] == cnt && even[i] == 0)
                ans[anum++] = i;
            else if (cnt == 1 && edge_type[i << 1] == 1)
                ans[anum++] = i;
        printf("%d\n", anum);
        for (int i = 0; i < anum; i++)
            printf("%d ", ans[i] + 1);
    }
    return 0;
}