Go: package main

import (
    "bufio"
    "os"
    "fmt"
)

var sc = bufio.NewScanner(os.Stdin)

/**************  Cell  *****************/
type Cell struct {
    item interface{}
    next *Cell
    prev *Cell
}

func NewCell(x interface{}, ne *Cell, pr *Cell) *Cell {
    newCp := new(Cell)
    newCp.item = x
    newCp.next = ne
    newCp.prev = pr
    return newCp
}
/************  End Cell  ***************/

/**************  Queue  ****************/
type Queue struct {
    size int
    front *Cell
    rear *Cell
}

func NewQueue() *Queue {
    return new(Queue)
}

func (q *Queue) Push(x interface{}) {
    newNode := NewCell(x, nil, nil)
    if q.size == 0 {
        q.front = newNode
        q.rear = newNode
    } else {
        newNode.prev = q.rear
        q.rear.next = newNode
        q.rear = newNode
    }
    q.size++
}

func (q *Queue) PopLeft() interface{} {
    if q.size == 0 {
        return nil
    } else {
        x := q.front.item
        if q.size == 1 {
            q.front = nil
            q.rear = nil
        } else {
            q.front = q.front.next
            q.front.prev = nil
        }
        q.size--
        return x
    }
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Length() int {
    return q.size
}

type State struct {
    color string
    cnt int
}

func main() {
    for {
        sc.Scan()
        init := sc.Text()
        if init == "0" {
            break
        }
        bfs(init)
    }
}

func bfs(init string) {
    dic := make(map[string]int)
    que := NewQueue()
    que.Push(State{init, 0})
    length := len(init)
    isSolved := false
    for !que.IsEmpty() {
        state := que.PopLeft().(State)
        _, ok := dic[state.color]
        if ok {
            continue
        } else {
            dic[state.color] = state.cnt
        }

        if isSingleColor(state.color) {
            fmt.Println(state.cnt)
            isSolved = true
            break
        }

        for i := 0;i < length - 1; i++ {
            color1, color2 := string(state.color[i]), string(state.color[i + 1])
            if color1 != color2 {
                color3 := other(color1, color2)
                if i <= length - 2 {
                    que.Push(State{state.color[:i] + color3 + state.color[i + 2:], state.cnt + 1})
                } else {
                    que.Push(State{state.color[:i] + color3, state.cnt + 1})
                }
            }
        }
    }
    if !isSolved {
        fmt.Println("NA")
    }
}

func other(color1, color2 string) string {
    if color1 == "r" {
        if color2 == "g" {
            return "bb"
        } else if color2 == "b" {
            return "gg"
        }
    } else if color1 == "g" {
        if color2 == "r" {
            return "bb"
        } else if color2 == "b" {
            return "rr"
        }
    } else if color1 == "b" {
        if color2 == "r" {
            return "gg"
        } else if color2 == "g" {
            return "rr"
        }
    }
    return ""
}

func isSingleColor(color string) bool {
    for _, c := range color {
        if string(c) != string(color[0]) {
            return false
        }
    }
    return true
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <set>

using namespace std;

//map<string,bool > passed;
map<string,int> dp;

const int INF=100000000;


int bfs(string str){

	//passed[str]=true;
	set<string> used;
	queue<string> *prv=new queue<string>();
	queue<string> *nxt=new queue<string>();
	int cnt=0;
	prv->push(str);
	while(prv->size()){
		while(prv->size()){
			string s = prv->front();
			prv->pop();
			char cl=s[0];
			bool f=false;
			for(int i = 1; i < s.size(); i++){
				if(s[i]!=cl){
					f=true;
					break;
				}
			}
			if(!f){
				delete prv,nxt;
				return cnt;
			}
			bool flag[200];
			int minCnt=INF;
			for(int i = 0; i < s.size()-1; i++){
				flag['r']=false;
				flag['g']=false;
				flag['b']=false;
				if(s[i]!=s[i+1]){
					flag[s[i]]=true;
					flag[s[i+1]]=true;
					if(!flag['r']){
						string nstr=s;
						nstr[i]='r';
						nstr[i+1]='r';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
						//minCnt=min(minCnt,dfs(nstr)+1);
//						passed[str]=false;
					}
					else if(!flag['g']){
						string nstr=s;
						nstr[i]='g';
						nstr[i+1]='g';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
//						minCnt=min(minCnt,dfs(nstr)+1);
//						passed[str]=false;
					}
					else if(!flag['b']){
						string nstr=s;
						nstr[i]='b';
						nstr[i+1]='b';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
//						passed[str]=true;
	//					minCnt=min(minCnt,dfs(nstr)+1);
	//					passed[str]=false;
					}
				}
			}
		}
		swap(prv,nxt);
		cnt++;
	}
	delete prv,nxt;
	return INF;
}

//int dfs(string str){
//	//if(dp.find(str)!=dp.end()){
//	//	return dp[str];
//	//}
//	if(passed.find(str)!=passed.end()&&passed[str]){
//		return INF;
//	}
////	cout<<str<<endl;
//	char cl=str[0];
//	bool f=false;
//	for(int i = 1; i < str.size(); i++){
//		if(str[i]!=cl){
//			f=true;
//			break;
//		}
//	}
//	if(!f)
//		return 0;
//
//	bool flag[200];
//	int minCnt=INF;
//	for(int i = 0; i < str.size()-1; i++){
//		flag['r']=false;
//		flag['g']=false;
//		flag['b']=false;
//		if(str[i]!=str[i+1]){
//			flag[str[i]]=true;
//			flag[str[i+1]]=true;
//			if(!flag['r']){
//				string nstr=str;
//				nstr[i]='r';
//				nstr[i+1]='r';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//			else if(!flag['g']){
//				string nstr=str;
//				nstr[i]='g';
//				nstr[i+1]='g';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//			else if(!flag['b']){
//				string nstr=str;
//				nstr[i]='b';
//				nstr[i+1]='b';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//		}
//	}
//	//if(minCnt!=INF)
////	dp[str]=minCnt;
//	return minCnt;
//}

int main(){

	string str;
	while(cin>>str&&str!="0"){
		//dp.clear();
		//passed.clear();
		//int ret=dfs(str);
		int ret=bfs(str);
		if(ret!=INF)
			cout<<ret<<endl;
		else
			cout<<"NA"<<endl;
	}


	return 0;
}

C++: #include <cstdio>
#include <queue>
#include <string>
#include <set>
#include <algorithm>

using namespace std;



bool judge(string s){
  for(int i = 1; i < s.length(); ++i) if(s[0] != s[i]) return false;
  return true;
}

int main(){
  char worm[16];
  while(scanf("%s", worm) && worm[0] != '0'){
    queue<string> q;
    q.push(string(worm));
    set<string>s;
    s.insert(string(worm));
    if(judge(q.front())){
      puts("0");
      continue;
    }
    int res = 1;
    while(!q.empty()){
      int q_size = (int)q.size();
      for(int j = 0; j < q_size; ++j){
	string tmp = q.front(); q.pop();
	int len = (int)tmp.length();
	for(int i = 0; i < len-1; ++i){
	  string n = tmp;
	  if(n[i] != n[i+1]){
	    if((n[i] == 'r' && n[i+1] == 'b') || (n[i] == 'b' && n[i+1] == 'r')) n[i] = n[i+1] = 'g';
	    else if((n[i]=='r'&&n[i+1]=='g') || (n[i]=='g'&&n[i+1]=='r')) n[i] = n[i+1] = 'b';
	    else if((n[i]=='g'&&n[i+1]=='b') || (n[i]=='b'&&n[i+1]=='g')) n[i] = n[i+1] = 'r';
	  }
	  ///	  puts(n.c_str());
	  if(s.find(n) != s.end()) continue;

	  if(judge(n)){
	    printf("%d\n", res);
	    goto end;
	  }
	  s.insert(n);
	  q.push(n);
	}
      }
      //      printf("%d\n", res);
      //      for(int i = 0; i < f.size(); ++i) puts(f[i].c_str());
      //      queue<string>t;
      //      t = q;
      //      while(!t.empty()){ puts(t.front().c_str()); t.pop();}
      //      puts("");
      
      res++;
    }
    puts("NA");
  end:;

  }
  return 0;
}